package com.wwz.leetcode;

import org.junit.Test;

public class LeetCode215_01 {

    @Test
    public void test() {
        int[] nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int res = findKthLargest(nums, 4);
        System.out.println(res);
    }

    public static int findKthLargest(int[] nums, int k) {
        // 第k大就是 第 nums.length - k 小    比如第一大那么就是nums.length - 1 排在最后那个元素
        return getIndex(nums, 0, nums.length - 1, nums.length - k);
    }

    public static int getIndex(int[] nums, int left, int right, int k) {
        int index = quickSort(nums, left, right);
        if (k == index) {
            return nums[index];
        } else {
            return index < k ? getIndex(nums, index + 1, right, k) : getIndex(nums, left, index - 1, k);
        }
    }

    public static int quickSort(int[] nums, int left, int right) {
        int pviot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pviot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pviot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[right] = pviot;
        return right;
    }
}
